package com.zjw.algorithm.ready1;

import com.zjw.algorithm.utils.TreeNode;
import com.zjw.algorithm.utils.Utils;

public class _中序后序构建二叉树 {

    public static void main(String[] args) {
        TreeNode treeNode = new _中序后序构建二叉树().buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});

        System.out.println(Utils.toString(treeNode));
    }

    private int postIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        postIndex = postorder.length - 1;
        return buildTreeInner(inorder, postorder, 0, inorder.length - 1);
    }

    private TreeNode buildTreeInner(int[] inorder, int[] postorder, int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }

        int root = postorder[postIndex];

        int p = inLeft;
        while (inorder[p] != root) {
            p++;
        }

        TreeNode treeNode = new TreeNode(root);
        postIndex--;
        treeNode.right = buildTreeInner(inorder, postorder, p + 1, inRight);
        treeNode.left = buildTreeInner(inorder, postorder,  inLeft, p - 1);
        return treeNode;
    }
}
